package cn.edu.sjtu.stap.graph;

import java.util.*;

import cn.edu.sjtu.stap.util.*;

/**
 * Graph. It maintains a set of nodes and a set of edges.
 * 
 * @author William
 * 
 */
public class Graph implements IGraph, java.io.Serializable {
    private static final long serialVersionUID = 1L;

    /**
     * The set of nodes.
     */
    protected GraphNodeSet nodes = new GraphNodeSet();

    /**
     * The set of edges.
     */
    protected GraphEdgeSet edges = new GraphEdgeSet();

    /**
     * Swap the contents of two nodes.
     * 
     * @param n1
     *            The first node.
     * @param n2
     *            The second node.
     */
    public static void swap(Graph g, GraphNode n1, GraphNode n2) {
        String tmpNote = n1.note;
        long tmpId = n1.id;
        GraphEdgeSet tmpIncomingEdges = n1.incomingEdges;
        GraphEdgeSet tmpOutgoingEdges = n1.outgoingEdges;
        GraphNodeSet tmpSourceNodes = n1.sourceNodes;
        GraphNodeSet tmpDestinationNodes = n1.destinationNodes;

        n1.note = n2.note;
        n1.id = n2.id;
        n1.incomingEdges = n2.incomingEdges;
        n1.outgoingEdges = n2.outgoingEdges;
        n1.sourceNodes = n2.sourceNodes;
        n2.destinationNodes = n2.destinationNodes;

        n2.note = tmpNote;
        n2.id = tmpId;
        n2.incomingEdges = tmpIncomingEdges;
        n2.outgoingEdges = tmpOutgoingEdges;
        n2.sourceNodes = tmpSourceNodes;
        n2.destinationNodes = tmpDestinationNodes;
    }

    /**
     * Default constructor. Initialize the set of nodes and the set of edges.
     * 
     */
    public Graph() {
        // Empty.
    }

    /**
     * Add a node into this graph. If the node is already in this graph, it does
     * nothing.
     * 
     * @param node
     *            The node to add.
     */
    public void add(GraphNode node) {
        nodes.add(node);
    }

    /**
     * Add an edge into this graph. If the edge is already in this graph, it
     * does nothing. If the source node and destination node are not in this
     * graph, it adds them into this graph.
     * 
     * @param edge
     *            The edge to add.
     */
    public void add(GraphEdge edge) {
        boolean b = edges.add(edge);
        if (b) {
            GraphNode source = edge.getSourceNode();
            GraphNode destination = edge.getDestinationNode();

            nodes.add(source);
            nodes.add(destination);
        }
    }

    /**
     * Add an edge(from, to) into this graph. If the edge is already in this
     * graph, it does nothing. If either of the from node and the to node are
     * not in this graph, it adds them into this graph.
     * 
     * @param from
     *            Source node of this edge.
     * @param to
     *            Destination node of this edge.
     */
    public void add(long id, GraphNode from, GraphNode to) {
        Iterator<GraphEdge> i = edges.iterator();
        while (i.hasNext()) {
            GraphEdge edge = i.next();
            if (edge.getId() == id) {
                return;
            }
        }
        nodes.add(from);
        nodes.add(to);
        GraphEdge edge = new GraphEdge(id, from, to);
        edges.add(edge);
    }

    /**
     * Add a graph into this graph. After adding, the given graph becomes a
     * sub-graph of this graph, that is the given graph's nodes and edges become
     * a part of this graph's.
     * 
     * @param graph
     *            The graph to add into this graph.
     */
    public void add(Graph graph) {
        nodes.addAll(graph.nodes);
        edges.addAll(graph.edges);
    }

    /**
     * Clear all the nodes and edges in this graph.
     * 
     */
    public void clear() {
        nodes.clear();
        edges.clear();
    }

    /**
     * Check whether a node is in this graph.
     * 
     * @param node
     *            The node to check.
     * @return true if the given node is in this graph, otherwise false.
     */
    public boolean contains(GraphNode node) {
        return nodes.contains(node);
    }

    /**
     * Check whether an edge is in this graph.
     * 
     * @param edge
     *            The edge to check.
     * @return true if the given edge is in this graph, otherwise false.
     */
    public boolean contains(GraphEdge edge) {
        return edges.contains(edge);
    }

    /**
     * Check whether the edge(from, to) exists in this graph.
     * 
     * @param from
     *            Source node.
     * @param to
     *            Destination node.
     * @return true if an edge from the source node to the destination node
     *         exists in this graph, otherwise false.
     */
    public boolean contains(GraphNode from, GraphNode to) {
        boolean b = nodes.contains(from) && nodes.contains(to);
        if (b) {
            b = false;
            Iterator<GraphEdge> i = edges.iterator();
            while (i.hasNext()) {
                GraphEdge edge = i.next();
                if (b = edgeEquals(edge, from, to)) {
                    break;
                }
            }
        }

        return b;
    }

    /**
     * Remove a node from this graph. Meanwhile, the edges that are related to
     * it will be also removed, and the nodes that are related to it will be
     * modified. If the node is not in this graph, it does nothing.
     * 
     * @param node
     *            The node to remove.
     * @return true if the given node is removed, otherwise false.
     */
    public boolean remove(GraphNode node) {
        boolean b = nodes.remove(node);
        if (b) {
            // Get all the edges to remove from this graph that are related to
            // the given node.
            GraphEdgeSet tmpEdges = this.getEdges();
            Iterator<GraphEdge> tmpIt = tmpEdges.iterator();
            while (tmpIt.hasNext()) {
                GraphEdge e = tmpIt.next();
                if (!node.containsIncomingEdge(e) && !node.containsOutgoingEdge(e)) {
                    // Not relate to this node.
                    tmpIt.remove();
                }
            }

            Iterator<GraphEdge> i = tmpEdges.iterator();
            while (i.hasNext()) {
                GraphEdge edge = i.next();

                remove(edge);
            }
        }

        return b;
    }

    /**
     * Remove all the edge(from, to) from this graph.
     * 
     * @param from
     *            Source node.
     * @param to
     *            Destination node.
     * @return true if all the edge(from, to) is removed from this graph,
     *         otherwise false.
     */
    public boolean remove(GraphNode from, GraphNode to) {
        boolean b = contains(from) && contains(to);
        if (b) {
            GraphEdgeSet tmpEdges = new GraphEdgeSet();

            Iterator<GraphEdge> i = edges.iterator();
            while (i.hasNext()) {
                GraphEdge edge = i.next();
                if (edgeEquals(edge, from, to)) {
                    // Call the remove() method of this graph to remove an edge.
                    tmpEdges.add(edge);
                }
            }

            i = tmpEdges.iterator();
            while (i.hasNext()) {
                remove(i.next());
            }
        }

        return b;
    }

    /**
     * Remove an edge from this graph and modify related nodes with it. If the
     * edge is not in this graph, it does nothing.
     * 
     * @param edge
     *            The edge to remove.
     * @return true if the given edge is removed, otherwise false.
     */
    public boolean remove(GraphEdge edge) {
        boolean b = edges.remove(edge);
        if (b) {
            GraphNode sourceNode = edge.getSourceNode();
            GraphNode destinationNode = edge.getDestinationNode();

            // Does not work! Because the first remove cause some field to be
            // null,
            // then the second cannot work propoerly!
            // sourceNode.removeOutgoingEdge(edge);
            // destinationNode.removeIncomingEdge(edge);

            if (sourceNode != null) {
                sourceNode.outgoingEdges.remove(edge);
                sourceNode.destinationNodes.remove(destinationNode);
            }
            if (destinationNode != null) {
                destinationNode.incomingEdges.remove(edge);
                destinationNode.sourceNodes.remove(sourceNode);
            }

            edge.sourceNode = null;
            edge.destinationNode = null;
        }

        return b;
    }

    /**
     * Get all the edges(from, to).
     * 
     * @param from
     *            Source Node.
     * @param to
     *            Destination Node.
     * @return all the edges whose source node is <code>from</code>, and
     *         destination node is <code>to</code>.
     */
    public GraphEdge[] getEdges(GraphNode from, GraphNode to) {
        ArrayList<GraphEdge> r = new ArrayList<GraphEdge>();
        Iterator<GraphEdge> i = edges.iterator();
        while (i.hasNext()) {
            GraphEdge edge = i.next();
            if (edgeEquals(edge, from, to)) {
                r.add(edge);
            }
        }

        return r.toArray(new GraphEdge[1]);
    }

    /**
     * Check whether the given edge equals to (from, to).
     * 
     * @param edge
     *            The edge to check.
     * @param from
     *            The node the edge to start with.
     * @param to
     *            The node the edge to end with.
     * @return true if the given edge starts with the <code>from</code> node,
     *         ends with the <code>to</code> node.
     */
    private boolean edgeEquals(GraphEdge edge, GraphNode from, GraphNode to) {
        if (edge == null) {
            return false;
        }

        GraphNode sourceNode = edge.getSourceNode();
        GraphNode destinationNode = edge.getDestinationNode();
        if (sourceNode != null && destinationNode != null && sourceNode.equals(from) && destinationNode.equals(to)) {
            return true;
        } else {
            return false;
        }
    }

    public void difference(Graph g) {
        GraphComponentSet<GraphEdge> tmpEdgeSet = this.edges.difference(g.edges);
        this.edges.clear();
        this.edges.addAll(tmpEdgeSet);

        GraphComponentSet<GraphNode> tmpNodeSet = this.nodes.difference(g.nodes);
        this.nodes.clear();
        this.nodes.addAll(tmpNodeSet);
    }

    /**
     * Get all the edges from this graph.
     */
    public GraphEdgeSet getEdges() {
        GraphEdgeSet result = new GraphEdgeSet();
        result.addAll(edges);

        return result;
    }

    /**
     * Get all the nodes from this graph.
     */
    public GraphNodeSet getNodes() {
        GraphNodeSet result = new GraphNodeSet();
        result.addAll(nodes);

        return result;
    }

    /**
     * Get the size of edge set.
     */
    public int getSizeOfEdges() {
        return edges.size();
    }

    /**
     * Get the size of node set.
     */
    public int getSizeOfNodes() {
        return nodes.size();
    }

    /*
     * (non-Javadoc)
     * 
     * @see cn.edu.sjtu.stap.graph.IGraph#traverse(cn.edu.sjtu.stap.graph.GraphVisitor)
     */
    public void traverse(GraphVisitor v) {
        Iterator<GraphNode> nodeIterator = nodes.iterator();

        while (nodeIterator.hasNext()) {
            GraphNode node = nodeIterator.next();
            if (v.visit(node)) {
                v.endVisit(node);
            }
        }

        Iterator<GraphEdge> edgeIterator = edges.iterator();

        while (edgeIterator.hasNext()) {
            GraphEdge edge = edgeIterator.next();
            if (v.visit(edge)) {
                v.endVisit(edge);
            }
        }
    }

    /*
     * (non-Javadoc)
     * 
     * @see cn.edu.sjtu.stap.graph.IGraph#traverse(cn.edu.sjtu.stap.graph.GraphVisitor,
     *      int)
     */
    public void traverse(GraphVisitor v, int visitOrder) {
        switch (visitOrder) {
        case NO_ORDER_TRAVERSE:
            noOrderTraverse(v);
            break;
        case DFS_TRAVERSE:
            dfsTraverse(v);
            break;
        case BFS_TRAVERSE:
            bfsTraverse(v);
            break;
        default:
            throw new IllegalArgumentException("The visit order is undefined!");
        }
    }

    /**
     * Traverse all the nodes with the order in the component sets. Typically it
     * is used while ignoring the relationship between the nodes. It fetches the
     * first node in the node set, and then the next and the one after the next,
     * etc.
     * 
     * @param v
     *            GraphVisitor perform the tasks while traversing each node.
     */
    private void noOrderTraverse(GraphVisitor v) {
        Iterator<GraphNode> i = nodes.iterator();

        while (i.hasNext()) {
            GraphNode node = i.next();

            if (v.visit(node)) {
                v.endVisit(node);
            }
        }
    }

    /**
     * Traverse all the nodes with the depth-first order. It fetches the first
     * node in the node set, and pushes it onto a stack, After that, it pops the
     * top of the stack, visits it, and pushes all the nodes who has incoming
     * edges from that node onto the stack. Continue with the top of the stack.
     * After one node is visited, it is put into a set which is used to record
     * all the nodes that has been visited. So before visiting a node, it is
     * checked whether it is visited. If it has been visited, it will not be
     * visited again.
     * 
     * @param v
     *            GraphVisitor perform the tasks while traversing each node.
     */
    private void dfsTraverse(GraphVisitor v) {
        GraphNodeSet visited = new GraphNodeSet();

        while (!visited.equals(nodes)) {
            // Get a node that has not been visited.
            GraphNode node = nodes.difference(visited).iterator().next();
            Stack<GraphNode> stack = new Stack<GraphNode>();
            stack.push(node);

            while (!stack.isEmpty()) {
                GraphNode n = stack.pop();
                if (!visited.contains(n) && v.visit(n)) {
                    v.endVisit(n);

                    // Get all the related nodes and push them into the stack.
                    Iterator<GraphEdge> i = n.getOutgoingEdgeSet().iterator();
                    while (i.hasNext()) {
                        stack.push(i.next().getDestinationNode());
                    }
                    visited.add(n);
                }
            }
        }
    }

    /**
     * Traverse all the nodes with the breadth-first order.
     * 
     * @param v
     */
    private void bfsTraverse(GraphVisitor v) {
        GraphNodeSet visited = new GraphNodeSet();

        while (!visited.equals(nodes)) {
            // Get a node that has not been visited.
            GraphNode node = nodes.difference(visited).iterator().next();

            // Nodes to visit.
            List<GraphNode> list1 = new ArrayList<GraphNode>();

            // Nodes added after visiting some nodes.
            List<GraphNode> list2 = new ArrayList<GraphNode>();
            List<GraphNode> tmp = null; // This is only for swap.
            list1.add(node);

            while (!list1.isEmpty()) {
                int size = list1.size();

                for (int i = 0; i < size; ++i) {
                    GraphNode n = list1.get(i);
                    if (!visited.contains(n) && v.visit(n)) {
                        v.endVisit(n);

                        // Get all the related nodes and push them into the
                        // stack.
                        Iterator<GraphEdge> edgeIterator = n.getOutgoingEdgeSet().iterator();
                        while (edgeIterator.hasNext()) {
                            list2.add(edgeIterator.next().getDestinationNode());
                        }
                        visited.add(n);
                    }
                }

                // Swap list1 and list2.
                tmp = list1;
                list1 = list2;
                list2 = tmp;
                list2.clear();
            }
        }
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#hashCode()
     */
    public int hashCode() {
        return edges.hashCode() + nodes.hashCode();
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object o) {
        if (o instanceof Graph) {
            Graph g = (Graph) o;

            return edges.equals(g.edges) && nodes.equals(g.nodes);
        }

        return false;
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    public String toString() {
        String n = nodes.toString();
        String e = edges.toString();

        return "Nodes: " + n + Utils.LINE_SEPARATOR + "Edges: " + e;
    }
}
